A Unified Framework for Tree Search Decoding : Rediscovering the Sequential Decoder

摘要

We consider receiver design for coded transmission over linear Gaussianchannels. We restrict ourselves to the class of lattice codes and formulate thejoint detection and decoding problem as a closest lattice point search (CLPS).Here, a tree search framework for solving the CLPS is adopted. In ourframework, the CLPS algorithm decomposes into the preprocessing and tree searchstages. The role of the preprocessing stage is to expose the tree structure ina form {\em matched} to the search stage. We argue that the minimum mean squareerror decision feedback (MMSE-DFE) frontend is instrumental for solving thejoint detection and decoding problem in a single search stage. It is furthershown that MMSE-DFE filtering allows for using lattice reduction methods toreduce complexity, at the expense of a marginal performance loss, and solvingunder-determined linear systems. For the search stage, we present a genericmethod, based on the branch and bound (BB) algorithm, and show that itencompasses all existing sphere decoders as special cases. The proposed genericalgorithm further allows for an interesting classification of tree searchdecoders, sheds more light on the structural properties of all known spheredecoders, and inspires the design of more efficient decoders. In particular, anefficient decoding algorithm that resembles the well known Fano sequentialdecoder is identified. The excellent performance-complexity tradeoff achievedby the proposed MMSE-Fano decoder is established via simulation results andanalytical arguments in several MIMO and ISI scenarios.